'''
转圈打印矩阵 【题目】 给定一个整型矩阵matrix，请按照转圈的方式打印它。 例如： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
打印结果为：1，2，3，4，8，12，16，15，14，13，9， 5，6，7，11， 10 【要求】 额外空间复杂度为O(1)
'''
def printEdge(m: list, tR: int, tC: int, dR: int, dC: int):
    if tR == dR:
        for i in range(tC, dC+1):
            print(f'{m[tR][i]}   ')
    elif tC == dC:
        for i in range(tR, dR+1):
            print(f'{m[tC][i]}   ')
    else:
        curC = tC
        curR = tR
        while curC != dC:
            print(f'{m[curR][curC]}   ')
            curC += 1
        while curR != dR:
            print(f'{m[curR][curC]}   ')
            curR += 1
        while curC != tC:
            print(f'{m[curR][curC]}   ')
            curC -= 1
        while curR != tR:
            print(f'{m[curR][curC]}   ')
            curR -= 1
def spiralOrderPrint(matrix: list) :
    tR = 0
    tC = 0
    dR = len(matrix) - 1
    dC = len(matrix[0]) - 1
    while tR <= dR and tC <= dC :
        printEdge(matrix, tR, tC, dR, dC)
        tR += 1
        tC += 1
        dR -= 1
        dC -= 1
def main():
    matrix = [[ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ],
				[13, 14, 15, 16 ]]
    spiralOrderPrint(matrix)
if __name__ == '__main__':
    main()
'''
旋转正方形矩阵 【题目】 给定一个整型正方形矩阵matrix，请把该矩阵调整成 顺时针旋转90度的样子。 【要求】 额外空间复杂度为O(1)。
'''
def rotate(m : list):
    tR = 0
    tC = 0
    dR = len(m) -1
    dC = len(m[0]) - 1
    while tR < dR:
        rotateEdge(m, tR, tC, dR, dC)
        tR += 1
        tC += 1
        dR -= 1
        dC -= 1
def rotateEdge(m: list, tR: int, tC: int, dR: int, dC: int):
    times = dC - tC
    for i in range(times):  #循环条件一定要沥青
        tmp = m[tR][tC+i]
        m[tR][tC+i] = m[dR-i][tC]
        m[dR-i][tC] = m[dR][dC-i]
        m[dR][dC-i] = m[tR+i][dC]
        m[tR+i][dC] = tmp

def printMatrix(m: list):
    for i in m:
        for j in i:
            print(f'{j}  ')
def main():
	matrix = [[ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ],
			[ 13, 14, 15, 16 ]]
	printMatrix(matrix)
	rotate(matrix)
	print("=========")
	printMatrix(matrix)
if __name__ == '__main__':
    main()
'''
'之'字形打印矩阵 【题目】 给定一个矩阵matrix，按照“之”字形的方式打印这 个矩阵，例如： 1 2 3 4 5 6 7 8 9 10 11 12 “之”字形打印的结果为：1，2，5，9，6，3，4，7，10，11， 8，12 【要求】 额外空间复杂度为O(1)。
'''
def printLevel(m: list, tR: int, tC: int, dR: int, dC: int, f: bool):
    if f :
        while tR != dR + 1 :
            print(f'{m[tR][tC]}  ')
            tR += 1
            tC -= 1
    else:
        while dR != tR - 1:
            print(f'{m[dR][dC]}  ')
            dR -= 1
            dC += 1

def printMatrixZigZag(matrix: list):
    tR = 0
    tC = 0
    dR = 0
    dC = 0
    endR = len(matrix) - 1
    endC = len(matrix[0]) - 1
    fromUp = False
    while tR != endR + 1 :
        printLevel(matrix, tR, tC, dR, dC, fromUp)
        tR = tR + 1 if tC == endC else tR
        tC = tC if tC == endC else tC + 1
        dC = dC + 1 if dR == endR else dC
        dR = dR if dR == endR else dR + 1
        fromUp = not fromUp

matrix = [[1, 2, 3, 4 ], [5, 6, 7, 8 ], [ 9, 10, 11, 12 ]]
printMatrixZigZag(matrix)

'''
在行列都排好序的矩阵中找数 【题目】 给定一个有N*M的整型矩阵matrix和一个整数K， matrix的每一行和每一 列都是排好序的。
实现一个函数，判断K 是否在matrix中。 例如： 0 1 2 5 2 3 4 7 4 4 4 8 5 7 7 9 如果K为7，返回true；如果K为6，返 回false。 
【要求】 时间复杂度为O(N+M)，额外空间复杂度为O(1)。
'''
def isContains(matrix: list, k: int) -> bool:
    row = 0
    colu = len(matrix[0]) - 1
    while row < len(matrix) and colu >= 0:
        if matrix[row][colu] == k:
            return True
        elif matrix[row][colu] > k:
            colu -= 1
        else : row += 1
    return False
matrix =[[ 0, 1, 2, 3, 4, 5, 6 ],# 0
            [ 10, 12, 13, 15, 16, 17, 18 ],# 1
            [ 23, 24, 25, 26, 27, 28, 29 ],# 2
            [ 44, 45, 46, 47, 48, 49, 50 ],# 3
            [ 65, 66, 67, 68, 69, 70, 71 ],# 4
            [ 96, 97, 98, 99, 100, 111, 122 ],# 5
            [ 166, 176, 186, 187, 190, 195, 200 ],# 6
            [233, 243, 321, 341, 356, 370, 380 ] # 7
]
K = 233
print(isContains(matrix, K))